# 377. 组合总和 Ⅳ

# 难度中等
# 给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。
# 请你从 nums 中找出并返回总和为 target 的元素组合的个数。
# 题目数据保证答案符合 32 位整数范围。

# 进阶：如果给定的数组中含有负数会发生什么？问题会产生何种变化？如果允许负数出现，需要向题目中添加哪些限制条件？

# 进阶问题
# 如果给定的数组中含有负数，则会导致出现无限长度的排列。

# 例如，假设数组 nums 中含有正整数 a 和负整数 −b（其中 a>0,b>0,−b<0），
# 则有 a×b+(−b)×a=0，对于任意一个元素之和等于 target 的排列，
# 在该排列的后面添加 b 个 a 和 a 个 −b 之后，得到的新排列的元素之和仍然等于 target，
# 而且还可以在新排列的后面继续 b 个 a 和 a 个 −b。因此只要存在元素之和等于 target 的排列，
# 就能构造出无限长度的排列。

# 如果允许负数出现，则必须限制排列的最大长度，避免出现无限长度的排列，才能计算排列数。

from typing import List


class Solution:

    def combinationSum4(self, nums: List[int], target: int) -> int:
        dp = [1] + [0] * target
        for i in range(1, target + 1):
            for num in nums:
                if i >= num:
                    dp[i] += dp[i - num]
        return dp[target]


if __name__ == '__main__':
    print(Solution().combinationSum4([1, 2, 3], 4))
